//题目:
// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

// 示例 1:
// 输入: [3,2,1,5,6,4], k = 2
// 输出: 5

// 示例 2:
// 输入: [3,2,3,1,2,4,5,5,6], k = 4
// 输出: 4

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

//代码:
class Solution 
{
    struct compare
    {
        bool operator()(int x,int y)
        {
            return x>y;
        }
    };
public:
    int quicksort(vector<int>& nums,int left,int right,int pos)
    {
        //找个基准值
        int std_val=nums[(left+right)/2];
        //三指针法区间划分
        int i=left-1,cur=left,j=right+1;
        while(cur<j)
        {
            if(nums[cur]<std_val) swap(nums[++i],nums[cur++]);
            else if(nums[cur]==std_val) cur++;
            else swap(nums[--j],nums[cur]);
        }
        //跳出循环后:[left,i]区域是小于std_val的; [i+1,j-1]是等于std_val的; [j,right]是大于std_val的
        if(pos>i && pos<j) return std_val;
        else if(pos<=i) return quicksort(nums,left,i,pos);
        else if(pos>=j) return quicksort(nums,j,right,pos);

        return -1;
    }
    int findKthLargest(vector<int>& nums, int k) 
    {
        //建小堆————nlog(k)
        // priority_queue<int,vector<int>,compare> pq;
        // for(auto x:nums)
        // {
        //     if(pq.size()<k) pq.push(x);
        //     else if(x>pq.top()) pq.pop(),pq.push(x);
        // }
        // return pq.top();

        //快排思想————快排过程中拿到nums[n-k]
        return quicksort(nums,0,nums.size()-1,nums.size()-k);
    }
};